#include<bits/stdc++.h>
#define gc getchar
#define itn int
#define x first
#define y second
#define eb emplace_back
#define em emplace
#define pb push_back
#define db double
#define y1 yy1_yyds
using namespace std; typedef long long ll; typedef unsigned long long ull;
// https://www.luogu.com.cn/discuss/522581 About "const"
ll read() {
	ll x = 0; short fh = 1; char ch = gc();
	while (!isdigit(ch)) {
		if (ch == '-') fh = -1;
		if (ch < 10) exit(0); 
		ch = gc();
	}
	while (isdigit(ch))
		x = x * 10 + (ch ^ 48), ch = gc();
	return fh * x;
}
#ifndef ONLINE_JUDGE
void debug() {cerr << "\n";}
template<typename Typ1> void debug(Typ1 arg) {cerr << arg << "\n";}
template<typename Typ1, typename ...Typ2> void debug(Typ1 arg, Typ2 ...args) {
	cerr << arg << " ", debug(args...);
}
#else
void debug() {}
template<typename Typ1> void debug(Typ1 arg) {}
template<typename Typ1, typename ...Typ2> void debug(Typ1 arg, Typ2 ...args) {}
#endif
void writeln(ll arg) {printf("%lld\n", arg);}
template<typename ...Typ2> void writeln(ll arg, Typ2 ...args) {
	printf("%lld ", arg), writeln(args...);
}
typedef pair <int, int> pii; typedef pair <ll, ll> pll;
const char Y_E_S[] = "YES", N__O[] = "NO";
// const char Y_E_S[] = "Yes", N__O[] = "No";
// #define infinite_testcase
// #define multiple_testcase
// #define output_Yes_No
const int DUST = 327, N = 114514, M = -1;
int n, k, q;
int a[N];
int act[N][3];
namespace Sub1 {
	void major() {
		for(int i = 1; i <= q; i++) {
			swap(a[act[i][0]], a[act[i][0] + 1]);
			int l = act[i][1], r = act[i][2];
			ll res = 0;
			for(int x = l; x <= r; x++) {
				int l = x, r = x, v = a[x];
				while(l != 1 || r != n) {
					while(a[l - 1] <= v) l--;
					while(a[r + 1] <= v) r++;
					if(l == 1 && r == n) break;
					v = min(a[l - 1], a[r + 1]), res++;
				}
			}
			res = res * k + (n - 1ll) * (r - l + 1);
			writeln(res);
		}
	}
}
namespace Sub2 {
	int lfa[N], rfa[N], lans[N], rans[N];
	int stk[N], top = 0;
	void run1() {
		for(int i = 1; i <= n; i++) {
			while(top && a[stk[top - 1]] < a[i]) {
				rfa[stk[--top]] = i;
			}
			stk[top++] = i;
		}
		while(top) rfa[stk[--top]] = 0;
		for(int i = n; i; i--) rans[i] = rfa[i] ? rans[rfa[i]] + 1 : 0;
	}
	void run2() {
		for(int i = n; i; i--) {
			while(top && a[stk[top - 1]] < a[i]) {
				lfa[stk[--top]] = i;
			}
			stk[top++] = i;
		}
		while(top) lfa[stk[--top]] = 0;
		for(int i = 1; i <= n; i++) lans[i] = lfa[i] ? lans[lfa[i]] + 1 : 0;
	}
	void major() {
		for(int i = 1; i <= q; i++) {
			swap(a[act[i][0]], a[act[i][0] + 1]);
			run1(), run2();
			
			int l = act[i][1], r = act[i][2];
			ll res = 0;
			for(int x = l; x <= r; x++) {
				res += lans[x] + rans[x];
				// int l = x, r = x, v = a[x];
				// while(l != 1 || r != n) {
					// while(a[l - 1] <= v) l--;
					// while(a[r + 1] <= v) r++;
					// if(l == 1 && r == n) break;
					// v = min(a[l - 1], a[r + 1]), res++;
				// }
			}
			res = res * k + (n - 1ll) * (r - l + 1);
			writeln(res);
		}
	}
}
namespace Sub3 {//AD
	int lfa[2][N], rfa[2][N], lans[2][N], rans[2][N];
	int stk[N], top = 0;
	void run1(int *rfa, int *rans) {
		for(int i = 1; i <= n; i++) {
			while(top && a[stk[top - 1]] < a[i]) {
				rfa[stk[--top]] = i;
			}
			stk[top++] = i;
		}
		while(top) rfa[stk[--top]] = 0;
		for(int i = n; i; i--) rans[i] = rfa[i] ? rans[rfa[i]] + 1 : 0;
	}
	void run2(int *lfa, int *lans) {
		for(int i = n; i; i--) {
			while(top && a[stk[top - 1]] < a[i]) {
				lfa[stk[--top]] = i;
			}
			stk[top++] = i;
		}
		while(top) lfa[stk[--top]] = 0;
		for(int i = 1; i <= n; i++) lans[i] = lfa[i] ? lans[lfa[i]] + 1 : 0;
	}
	ll ans[2][N];
	void major() {
		run1(rfa[0], rans[0]), run2(lfa[0], lans[0]);
		swap(a[act[1][0]], a[act[1][0] + 1]);
		run1(rfa[1], rans[1]), run2(lfa[1], lans[1]);
		for(int j = 0; j < 2; j++) for(int i = 1; i <= n; i++)
			ans[j][i] = ans[j][i - 1] + lans[j][i] + rans[j][i];
		for(int i = 1; i <= q; i++) {
			// swap(a[act[i][0]], a[act[i][0] + 1]);
			// run1(), run2();
			
			int l = act[i][1], r = act[i][2];
			ll res = ans[i & 1][r] - ans[i & 1][l - 1];
			res = res * k + (n - 1ll) * (r - l + 1);
			writeln(res);
		}
	}
}
bool major(int Case = 1) {
	n = read(), k = read();
	for(int i = 1; i <= n; i++) a[i] = read();
	a[0] = a[n + 1] = 2e9;
	q = read();
	for(int i = 1; i <= q; i++) {
		act[i][0] = read(), act[i][1] = read(), act[i][2] = read();
	}
	if(n <= 100 && q <= 100) 
		return Sub1::major(), 0;
	if(n <= 1000 && q <= 1000)
		return Sub2::major(), 1;
	return Sub3::major(), 0;
	return Case ^= Case ^ Case;
}
void initial_function(int argc, char **argv) {
	**argv = argc; /* <- place_holder
	you won't give up no matter what happens, will you?
	code time: 00:
	---
	
	*/
	freopen("summer.in", "r", stdin);
	freopen("summer.out", "w", stdout);
}
signed main(int argc, char **argv) {
	initial_function(argc, argv);
	int Case = 1, Maxcase = 1;
	for (
#ifdef multiple_testcase
		  Maxcase = read()
#endif
				     	  ;
#ifndef infinite_testcase
							Case <= Maxcase
#endif
				     					   ; Case++)
#ifdef output_Yes_No
		puts(major(Case) ? Y_E_S : N__O);
#else
		major(Case);
#endif
	return DUST ^ 0x147;
}
